package exercises.newcoder.solution;

import exercises.newcoder.util.ListNode;

/**
 * <a href="https://www.nowcoder.com/practice/d75c232a0405427098a8d1627930bea6?tpId=202&&tqId=38713&rp=1&ru=/activity/oj&qru=/ta/code-written-high/question-ranking">
 * WC4 链表排序</a>
 *
 * @author or2
 * @Description 在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
 * @create 2021年09月13日 时间: 8:57
 */
public class SortList {

    /**
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
//        添加辅助 头结点
        ListNode headAux = new ListNode(0);
        headAux.next = head;
//        归并排序
        ListNode end = head;
        while (end.next != null) {
            end = end.next;
        }
        mergeSort(headAux, end);
        return headAux.next;
    }

    /**
     * 归并 递归 排序
     *
     * @param startPre 开始结点的头结点
     * @param endAfter 下一个链表的头结点
     * @return
     */
    private ListNode mergeSort(ListNode startPre, ListNode endAfter) {
//        归并 - 终止条件
        if (startPre == endAfter || startPre.next == endAfter) {
            return endAfter;
        }
//        快慢指针 - 二分
        ListNode quick = startPre;
        ListNode slow = quick;
        while (slow != endAfter) {
            quick = quick.next;
            slow = slow.next;
            if (slow == endAfter) {
                break;
            }
            slow = slow.next;
        }
//        向下归并 (]
        ListNode last = mergeSort(startPre, quick);
//        修正区间
        if (last.val > quick.val) {
            quick = last;
        }
        last = mergeSort(quick, endAfter);
        if (last.val > endAfter.val) {
            endAfter = last;
        }
        /*mergeSort(quick, slow);*/
//        合并排序
        return merge(startPre, quick, endAfter);
    }

    /**
     * 归并 的 合并操作
     *
     * @param startPre 链表 ① 的头结点
     * @param quick    链表 ② 的头结点 - 链表 ① 的最后一个阶段
     * @param endAfter 链表 ② 的最后一个结点, 下一个链表的头结点
     * @return 合并后的右区间最后一个结点
     */
    private ListNode merge(ListNode startPre, ListNode quick, ListNode endAfter) {
//        链表 ② 的后续链表, 断链
        ListNode sequel = endAfter.next;
        endAfter.next = null;
//        链表 ① 的后续链表, 断链
        ListNode q = quick.next;
        quick.next = null;
//        合并两个链表
        ListNode p = startPre;
        while (p.next != null && q != null) {
            if (p.next.val <= q.val) {
                p = p.next;
            } else {
                ListNode qNect = q.next;
                q.next = p.next;
                p.next = q;
                p = q;
                q = qNect;
            }
        }

//        若链表 ① 先走完
        if (p == quick) {
            /*if (p.next == null) {*/
            while (q != null) {
                ListNode qNect = q.next;
                q.next = null;
                /*属性赋值idea也查, 误报*/
                p.next = q;
                p = q;
                q = qNect;
            }
//            接续链表 (对应断链)
            p.next = sequel;
            return p;
        } else {
//            接续链表 (对应断链)
            quick.next = sequel;
            return quick;
        }
    }
}